#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

int maxProfit(vector<int>& prices) {
    int total = 0, buy = prices[0], sell = 0;

    for (int i = 0; i < prices.size() - 1; i++)
    {
        if (prices[i] <= prices[i + 1])
        {
            sell = prices[i + 1];
        }
        if (prices[i] > prices[i + 1])
        {
            if (sell != 0)
            {
                total += sell - buy;
                buy = prices[i + 1];
                sell = buy;
            }
            else
            {
                buy = prices[i + 1];
                sell = buy;
            }
        }
    }
    if (sell > buy) total += sell - buy;
    return total;
}

int largestSumAfterKNegations(vector<int>& nums, int k) {
    int m = 0;
    for (auto x : nums)
    {
        if (x < 0)
            m++;
    }
    if (m == k)
    {
        for (auto x : nums)
        {
            if (x < 0)
                x = -x, k--;
            if (k == 0)
                break;
        }
    }
    else if (m > k)
    {
        vector<int> v;
        for (auto x : nums)
        {
            if (x < 0)
                v.push_back(x);
        }
        while (k--)
        {
            int min = v[0];
            int j = 0;
            for (int i = 0; i < v.size(); i++)
            {
                if (v[i] < min)
                    min = v[i], j = i;
            }
            v[j] = -v[j];
            for (auto x : nums)
                if (x == min)
                {
                    x = -x;
                    break;
                }
        }
    }
    else
    {
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] < 0)
            {
                nums[i] = -nums[i];
                k--;
            }
        }
        if (k % 2 != 0)
        {
            int min = nums[0];
            int j = 0;
            for (int i = 1; i < nums.size(); i++)
                if (nums[i] < min)
                    min = nums[i], j = i;
            nums[j] = -nums[j];
        }
    }
    int ret = 0;
    for (auto x : nums)
        ret += x;
    return ret;
}

//vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
//    int n = heights.size();
//    vector<int> index(n);
//    for (int i = 0; i < heights.size(); i++)
//    {
//        index[i] = i;
//    }
//    sort(index.begin(), index.end(), [&](int i, int j) {
//        return heights[i] > heights[j];
//        });
//    vector<string> ans;
//    for (auto x : index)
//    {
//        ans.push_back(names[x]);
//    }
//    return ans;
//}


int main()
{
    vector<int> v1{ 180,165,170 };
    vector<string> v2{ "Mary","John","Emma" };
    //maxProfit(v);
    //largestSumAfterKNegations(v, 3);
    //sortPeople(v2, v1);
    

	return 0;
}